Many state-of-the-art processing devices, such as, for example, a tablet personal computer (PC), or other processing device, permit a user to provide input as digital ink. The digital ink may include one or more handwritten strokes, which a processing device may display as ink as the one or more handwritten strokes are input. A handwritten stroke may begin when a writing instrument lands on a writing surface, and may end when the writing instrument is lifted off the writing surface. The writing surface may include a display screen, which may further include a digitizer, and the writing instrument may be an electronic or non-electronic pen, a stylus, a user's own finger, a pointing device, such as, for example, a computer mouse, or another writing instrument.
A user may input one or more handwritten strokes, as digital ink, to form a two-dimensional structure. The two-dimensional structure may include a mathematical expression, a chemical formula, textual characters, numbers, or other two-dimensional structures.
One problem with respect to recognizing handwritten mathematical expressions is parsing. Parsing is a process in which an input sequence is analyzed in order to determine its structure, such as, for example, mathematical objects included in a mathematical expression. The input sequence may include a number of handwritten strokes or typeset mathematical symbols. In parsing, a terminal object, or atom is not dividable and may include only one stroke.
A region, R, may include a number of strokes, which are included in a mathematical expression. Separation of the number of strokes in a region into multiple regions is called partitioning. Existing parsing algorithms attempt to partition a region, R, including a number of strokes, into two regions, R1 and R2, each of which may include a subset of the strokes of the region, R. The parsing algorithms may further partition region R1 into two regions, R11 and R12, each of which may include a subset of the strokes of region R1. The parsing algorithms may further partition region R2 into two regions, R21 and R22, each of which may include a subset of the strokes of region R2.
In general, if region R can be divided into regions R1 and R2, such that R1∩R2=0, R1∪R2=R and sub-regions R1 and R2 are not empty, then regions R1 and R2 create a partition P=[R1, R2] of the region R. A number of all possible partitions of the region R may be exponential in relation to a number of terminal objects. As an example, if region R includes N terminal objects, then a number of all sub-regions is 2N−2 (this includes all subsets of a region R not including itself and an empty set), which is exponential. A method which analyzes an exponential number of sub-regions created from a single region is time-consuming and unpractical. Therefore, existing parsing algorithms include rules to prune a number of regions and partitions created.
Previous methods of partitioning a region fail under certain circumstances. For example, a Rectangle Hull Region (RHULL), which is defined as a smallest axis aligned rectangle which includes one or more strokes, cannot be used to separate a square-root symbol from the one or more objects upon which the square-root symbol acts. For example, with respect to “√{square root over (X)}”, “√{square root over ( )}” cannot be separated from “X”.
An object is convex if for every pair of points within the object, every point on a straight line segment that joins each of the pair of points is within the object. A Convex Hull Region (CHULL), is defined as a smallest convex region which contains one or more strokes. A first version of Convex Hull Region (CHULL1) creates a partition if and only if:CHULL(R1)∩CHULL(R2)=0.A second version of Convex Hull Region (CHULL2) creates a partition if and only if:CHULL(R1)∩R2=0 or R1∩CHULL(R2)=0.Among RHULL, CHULL1 and CHULL2, only CHULL2 is capable of parsing certain handwritten expression which include a superscript. However, RHULL, CHULL1 and CHULL2 are not capable of parsing a fraction when a portion of a numerator crosses a horizontal fraction line.
Although, CHULL2 is capable of parsing expressions which RHULL and CHULL cannot, one flaw of the CHULL2 parsing algorithm is that CHULL2 does not efficiently enumerate all partitions. An upper bound of complexity of CHULL2 is exponential.